package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/design-linked-list/">设计链表(Design Linked List)</a>
 * <p>你可以选择使用单链表或者双链表，设计并实现自己的链表。</p>
 * <p>单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。</p>
 * <p>如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。</p>
 * <p>
 * 实现 MyLinkedList 类：
 * <ul>
 *     <li>MyLinkedList() 初始化 MyLinkedList 对象。</li>
 *     <li>int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。</li>
 *     <li>void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。</li>
 *     <li>void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。</li>
 *     <li>void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。</li>
 *     <li>void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。</li>
 * </ul>
 * </p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例：
 *      输入
 *          ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
 *          [[], [1], [3], [1, 2], [1], [1], [1]]
 *      输出
 *          [null, null, null, null, 2, null, 3]
 *      解释
 *          MyLinkedList myLinkedList = new MyLinkedList();
 *          myLinkedList.addAtHead(1);
 *          myLinkedList.addAtTail(3);
 *          myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
 *          myLinkedList.get(1);              // 返回 2
 *          myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
 *          myLinkedList.get(1);              // 返回 3
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 * <li>0 <= index, val <= 1000</li>
 * <li>请不要使用内置的 LinkedList 库。</li>
 * <li>调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @see LC0705DesignHashSet_S 设计哈希集合(Design HashSet)
 * @see LC0706DesignHashMap_S 设计哈希映射(Design HashMap)
 * @see LC707DesignLinkedList_M 设计链表(Design Linked List)
 * @see LC1206DesignSkiplist_H 设计跳表(Design Skiplist)
 * @since 2023/5/10 10:06
 */
public class LC707DesignLinkedList_M {

    public static class MyLinkedList {

        final Node head;
        final Node tail;
        int size;

        public MyLinkedList() {
            head = new Node(-1);
            tail = new Node(-1);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }

        public int get(int index) {
            if (index < 0 || index >= size) {
                return -1;
            }
            Node currNode = head;
            for (int i = 0; i <= index; ++i) {
                currNode = currNode.next;
            }
            return currNode.val;
        }

        public void addAtHead(int val) {
            addAtIndex(0, val);
        }

        public void addAtTail(int val) {
            addAtIndex(size, val);
        }

        public void addAtIndex(int index, int val) {
            if (index < 0 || index > size) {
                return;
            }
            Node currNode = head;
            for (int i = 0; i < index; ++i) {
                currNode = currNode.next;
            }
            Node newNode = new Node(val);
            newNode.next = currNode.next;
            newNode.prev = currNode;
            currNode.next.prev = newNode;
            currNode.next = newNode;
            ++size;
        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index >= size) {
                return;
            }
            Node currNode = head;
            for (int i = 0; i < index; ++i) {
                currNode = currNode.next;
            }
            currNode.next.next.prev = currNode;
            currNode.next = currNode.next.next;
            --size;
        }

        private static class Node {
            final int val;
            Node prev;
            Node next;

            public Node(int val) {
                this.val = val;
            }
        }
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.addAtHead(1);
        myLinkedList.addAtTail(3);
        myLinkedList.addAtIndex(1, 2);
        System.out.println(myLinkedList.get(1));    // 1
        myLinkedList.deleteAtIndex(1);
        System.out.println(myLinkedList.get(1));    // 3
    }
}
